In a public key cryptographic scheme, a public/private key pair is selected so that the problem of deriving the private key from the corresponding public key is equivalent to solving a computational problem that is believed to be intractable. One commonly used public key scheme is based on integer factorization in finite groups, in particular the RSA public key system for modulus n=p·q, where p and q are primes.
Other public key schemes are based on the discrete logarithm problem in finite groups, in particular Diffie-Hellman key exchange and the ElGamal protocol in Zp (p being a prime), and their variants such as the digital signature algorithm (DSA).
Elliptic curve public key schemes are based on the elliptic curve (EC) discrete logarithm problem, whose hardness is the basis for the security of EC cryptographic (ECC) schemes, including the EC digital signature algorithm (ECDSA). ECC is typically defined over two types of fields, Fp and F2m, or generally Fq, where the distinction is not important.
ECC public key schemes are often chosen for being particularly efficient and secure. For instance, it has been demonstrated that smaller parameters can be used in ECC than RSA or other discrete log systems at a given security level. As such, many solutions using ECC have been developed.
The Elliptic Curve Pintsov-Vanstone Signature (ECPVS) scheme, as presented in the ASC X9.92 Draft, provides a digital signature scheme with partial message recovery. PV signatures can be done in other discrete log implementations, however EC is considered most desirable. The ECPVS scheme has been used to provide a level of confidentiality by enabling a portion of the message being signed to be “hidden” within one of the resultant signature components. However, in order for the hidden portion to remain confidential, the public key of the signer needs to be kept secret. In a closed system, this may be convenient, however, keeping the public key secret is not the norm for public key systems.
The ECPVS scheme starts with a signer A having a private/public key pair (dA, GA) on an elliptic curve, where dA is a long term private key and GA is a restricted public key that is shared amongst a select group of verifiers. In the signing algorithm, A signs a message M=N∥V, where N is the hidden portion of the message to be signed. The hidden portion has a predefined characteristic (such as a particular format), e.g. by containing a certain level of redundancy, and V is the plain text portion of the message. In ECPVS, the amount of redundancy or other characteristic can be chosen and thus upon recovering the hidden portion N when verifying the signature, the redundancy or other characteristic can be checked to verify the signature. The following summarizes ECPV signature generation.
1. Generate an ephemeral key pair (k, Q), where Q=kG is a point on the elliptic curve, and k is a random integer 1≦k<n, and n is the order of the group generated by the elliptic curve base point G.
2. Construct a key k1=KDF(Q), where KDF is a key derivation function. In general, a key derivation function is used to derive a secret key from a secret value and/or some known information. In ECPVS, KDF takes as an input a point, Q, and possibly other information, and generates an encryption key k1.
3. Compute a first signature component c as c=ENCk1 (N), i.e. the encryption of the message N using a key k1, where ENC is a suitable encryption scheme that takes as an input plaintext (e.g. N) and encrypts it with a key k1 to produce ciphertext c.
4. Compute an intermediate component hi as h=Hash(c∥V), where Hash is a suitable hash function, e.g. SHA1. If preferred, additional information that may be available or become available to parties verifying the signature (in other words information that the verifier needs ‘on the side’ for verification), e.g. a certificate or identifying information of the signer may be incorporated into h.
5. Convert the intermediate component h to an integer e.
6. Calculate a second signature component s using a suitable signature algorithm, such as the Schnorr algorithm, where: s=e·dA+k mod n.
7. Output the signature as (c, s, V) or (s, c∥V).
The following illustrates ECPV signature verification on a signature (s, c∥V), when provided with A's genuine public key GA.
1. Compute the intermediate component h, using the component c∥V and using the same hash function used in the signing stage and any additional information, such as the identification information of the signer, where: h=Hash(c∥V).
2. Convert h to an integer e.
3. Compute a representation Q′ of the ephemeral public key Q using the integer e, the public key of A, the base point G, and the signature component s, e.g. as Q′=sG−eGA.
4. Compute a decryption key k1′ using the same key derivation function KDF used in the signing stage, including the same additional information, namely as k1′=KDF(Q′).
5. Recover a representation N′ of the hidden portion N by decrypting the component c using the key derived in step 4 and a complementary decryption function DEC, namely as N′=DECk1′(c).
6. Check the specified characteristic (such as a particular format) of, e.g., redundancy contained in N′. If N′ contains the necessary characteristic such as a certain amount of redundancy, then N′ is a valid message and the signature is verified. If N′ does not contain the necessary redundancy, then a null and invalid signature is returned.
The above scheme has been used to hide messages in the signature, in environments where it is reasonable to keep the public key GA of A secret among a population of verifiers. This requires that the verifiers be trusted and/or controlled such that only they are able to use the public key and thus recover the portion N that is hidden in c. While in certain closed systems this may be plausible for providing confidentiality for the hidden portion to a group in the closed system, it is typically undesirable to have the public key be ‘secret’. There is therefore a need to provide true confidentiality in such a system without having to make the public key secret.